package 剑指Offer._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/15 19:56
 * 机器人的运动范围
 * 算法：广度优先搜索
 */
public class _13 {
    public static void main(String[] args) {
        System.out.println(new _13().movingCount(2, 3, 1));
    }
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, k, visited);
    }
    int dfs(int lx, int ly, int k, boolean[][] visited) {
        if (lx < 0 || lx >= visited.length || ly < 0 || ly >= visited[0].length ||
        (lx / 10 + lx % 10 + ly / 10 + ly % 10 > k) || visited[lx][ly]) return 0;
        visited[lx][ly] = true;
        return dfs(lx + 1, ly, k, visited) + dfs(lx, ly + 1, k, visited)
                + dfs(lx - 1, ly, k, visited) + dfs(lx, ly - 1, k, visited) + 1;
    }

}
